#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
#include<string>
using namespace std;

namespace lh
{
	//BM17 二分查找-I
	//https://www.nowcoder.com/practice/d3df40bd23594118b57554129cadf47b?tpId=295&tqId=1499549&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj
    class Solution1 {
    public:
        int search(vector<int>& nums, int target) {
            // write code here
            if (nums.empty())
                return -1;
            int left = 0;
            int right = nums.size() - 1;
            while (left <= right)
            {
                int mid = (left + right) / 2;
                if (nums[mid] == target)
                    return mid;
                if (nums[mid] > target)
                {
                    right = mid - 1;
                }
                else {
                    left = mid + 1;
                }
            }
            return -1;
        }
    };
    void test1()
    {
        vector<int>nums = { -1,0,3,4,6,10,13,14 };
        int target = 13;
        cout << Solution1().search(nums, target) << endl;
    }
    //BM18 二维数组中的查找
    //https://www.nowcoder.com/practice/abc3fe2ce8e146608e868a70efebf62e?tpId=295&tqId=23256&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj
    class Solution2 {
    public:
        bool Find(int target, vector<vector<int> > array) {
            //杨氏矩阵，线性搜索
            if (array.size() == 0)
                return false;
            //左下角开始搜索,上面的都<，右边的都>
            int row = array.size() - 1;
            int col = 0;
            while (row >= 0 && col < array[0].size())
            {
                if (array[row][col] < target)
                {
                    col++;
                }
                else if (array[row][col] > target)
                {
                    row--;
                }
                else {
                    return true;
                }
            }
            return false;
        }
    };
    void test2()
    {
        vector<vector<int>>array = { {1,2,8,9} ,{2,4,9,12},{4,7,10,13},{6,8,11,15} };
        int target = 7;
        cout << Solution2().Find(target, array) <<endl;
    }
    //BM19 寻找峰值
    //https://www.nowcoder.com/practice/fcf87540c4f347bcb4cf720b5b350c76?tpId=295&tqId=2227748&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj
    class Solution3 {
    public:
        int findPeakElement(vector<int>& nums) {
            // 二分法，取标杆元素划分区间。若标杆元素＜右边元素，则缩小范围至右区间（右边大，一定存在波峰）
            //若标杆元素>右边元素，则缩小范围至左区间（右边在减小，不一定存在波峰）
            int left = 0;
            int right = nums.size() - 1;
            while (left < right)
            {
                int mid = (left + right) / 2;
                //右边往下，不一定有波峰
                if (nums[mid] > nums[mid + 1])
                {
                    right = mid;
                }
                //右边往上，一定有波峰
                else if (nums[mid] < nums[mid + 1])
                {
                    left = mid + 1;
                }
            }
            return left;
        }
    };
    void test3()
    {
        vector<int>nums = { 2,4,1,2,7,8,4 };
        cout << Solution3().findPeakElement(nums) << endl;
    }
    //BM22 比较版本号
    //https://www.nowcoder.com/practice/2b317e02f14247a49ffdbdba315459e7?tpId=295&tqId=1024572&ru=/exam/oj&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Foj
    class Solution4 {
    public:

        int compare(string version1, string version2) {
            //采用双指针同时遍历2个字符串,将.作分界，每次比较区间数值大小
            int len1 = version1.size() - 1;
            int len2 = version2.size() - 1;
            int pt1 = 0;
            int pt2 = 0;
            //全部走完
            while (pt1 <= len1 || pt2 <= len2)
            {
                int num1 = 0;
                while (pt1 <= len1 && version1[pt1] != '.')
                {
                    num1 = num1 * 10 + (version1[pt1] - '0');
                    pt1++;
                }
                int num2 = 0;
                while (pt2 <= len2 && version2[pt2] != '.')
                {
                    num2 = num2 * 10 + (version2[pt2] - '0');
                    pt2++;
                }
                //跳过.
                pt1++;
                pt2++;
                //比较
                if (num1 < num2)
                {
                    return -1;
                }
                if (num1 > num2)
                {
                    return 1;
                }
            }
            return 0;
        }
    };
    void test4()
    {
        string s1 = "1.1";
        string s2 = "2.1";
        cout << Solution4().compare(s1, s2) << endl;
    }
}

int main()
{
    lh::test1();
    lh::test2();
    lh::test3();
    lh::test4();
    return 0;
}